
//小顶堆
export interface ComparisonHandler<T, R = boolean> {
    (source: T, dest?: T): R;
}
// 默认处理小顶堆如何判断大小的规则
export const comparisonHandler: ComparisonHandler<any, boolean> = function (dataA, dataB) {
    return dataA.date.getTime() < dataB.date.getTime();
};

// 默认获取 timeout 的规则
export const getTimeoutHandler: ComparisonHandler<any, number> = function (dataA, dataB) {
    return dataA.date.getTime() - new Date().getTime();
};

export class Heap<T> {
    _comparisonHandler: ComparisonHandler<T>;
    count: number = 0;
    list: T[] = [];
    constructor(comparisonHandler: ComparisonHandler<T, boolean>) {
        this._comparisonHandler = comparisonHandler;
        this.reset();
    }

    /**
     * 插入
     */
    insert(data: T) {
        this.list[this.count] = data;
        let newIndex = this.count;
        this.count++;
        let parentIndex = newIndex >> 1;

        while (
            parentIndex > 0 &&
            this._comparisonHandler(this.list[newIndex], this.list[parentIndex])
        ) {
            // 交换位置
            let temp = this.list[parentIndex];
            this.list[parentIndex] = this.list[newIndex];
            this.list[newIndex] = temp;
            newIndex = parentIndex;
            parentIndex = newIndex >> 1;
        }
    }

    /**
     * 删除堆顶最小元素
     * 因为是小顶堆，所有堆顶元素为最小元素
     */
    removeMin() {
        return this.removeByIndex(1);
    }

    /**
     * 基于 index 删除元素
     * @param {} i
     */
    removeByIndex(i: number) {
        if (!this.list[i]) return null;
        let removeData = this.list[i];
        this.count--;
        // 删除的是最后一个元素的话，只需要弹出 list 即可
        if (this.count === i) {
            this.list.pop();
        } else {
            this.list[i] = this.list.pop();
            this.heapify(i);
        }
        return removeData;
    }

    /**
     * 堆化
     * @param {} i
     */
    heapify(i: number) {
        while (true) {
            let minIndex = i;
            if (
                i * 2 < this.count &&
                this._comparisonHandler(this.list[i * 2], this.list[i])
            ) {
                minIndex = i * 2;
            }

            if (
                minIndex + 1 < this.count &&
                this._comparisonHandler(this.list[minIndex + 1], this.list[minIndex])
            ) {
                minIndex = minIndex + 1;
            }

            if (i === minIndex) break;

            // 交换位置
            let temp = this.list[i];
            this.list[i] = this.list[minIndex];
            this.list[minIndex] = temp;
            // 更新指针
            i = minIndex;
        }
    }

    peep() {
        return this.list[1];
    }

    empty() {
        return this.count === 1 && !this.list[1];
    }

    getList() {
        return this.list;
    }

    reset() {
        this.list = [];
        this.count = 1;
    }
};
